// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem115.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\115.不同的子序列.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-17 10:19:45
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-17 20:06:12
 */
/*
 * @lc app=leetcode.cn id=115 lang=cpp
 *
 * [115] 不同的子序列
 */

// @lc code=start
class Solution {
public:
    int numDistinct(string s, string t) {
        int s_size = s.size();
        int t_size = t.size();
        if(s_size < t_size)
            return 0;
        vector<vector<long>> dp(t_size + 1, vector<long>(s_size+1,0));
        for(int j = 0;j <= s_size;j++)
        {
            dp[0][j] = 1;
        }

        for(int i = 0 ;i < dp.size();i++)
        {
            for(int j = 0; j <dp[0].size() ; j++)
            {
                cout<< dp[i][j] << "  ";
            }
            cout<<endl;
        }
    
        // 开始规划
        for(int i = 1; i <= t_size ;i++)
        {
            for(int j = 1;j <= s_size ;j++)
            {
                if(s[i-1] == t[j-1])
                {
                    dp[i][j] = dp[i][j - 1] + dp[i-1][j-1];
                    int b = dp[i][j];
                }
                else
                {
                    dp[i][j] = dp[i][j - 1];
                    int a = dp[i][j];
                }
            }
        }
        return dp[t_size][s_size];
    }


};
// @lc code=end

